/*************************************************************************
    > File Name: 2.linklist.cpp
    > Author: zhangxu
    > Mail:
    > Created Time: 四  7/18 19:42:44 2024
 ************************************************************************/

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
// 单向链表
// 循环链表的头节点指向链表的最后一个节点
// 双向链表
typedef struct Node {
    int data;
    struct Node *next;
} Node;
// 初始化
Node *initNode(int val) {
    Node *p = (Node *)malloc(sizeof(Node));
    p->data = val;
    p->next = NULL;
    return p;
}
int nodeSize(Node *head) {
    int size = 0;
    for (Node *p = head; p; p = p->next) {
        size += 1;
    }
    return size;
}
// 插入
Node *insert(Node *head, int pos, int val) {
    if (pos == 0) {
        Node *new_node = initNode(val);
        new_node->next = head;
        return new_node;
    }
    Node *p = head;
    for (int i = 1; i < pos; i++) {
        p = p->next;
    }
    Node *new_node = initNode(val);
    new_node->next = p->next;
    p->next = new_node;
    return head;
}
Node *insertOpt(Node *head, int pos, int val) {
    Node virtual_head_node, *p = &virtual_head_node;
    Node *new_node = initNode(val);
    virtual_head_node.next = head;
    for(int i = 0; i < pos; i++) {
        p = p->next;
    }
    new_node->next = p->next;
    p->next = new_node;
    return virtual_head_node.next;
}
Node *pushFront(Node *head, int val) {
    Node *new_node = initNode(val);
    new_node->next = head;
    return new_node;
}

Node *pushBack(Node *head, int val) {
    Node *new_node = initNode(val);
    if (head == nullptr) {
        new_node->next = head;
        return new_node;
    }
    Node *p = head;
    while (p->next) {
        p = p->next;
    }
    p->next = new_node;
    return head;
}

void printLinklist(Node *head) {
    int size = nodeSize(head);
    for (int i = 0; i < size; i++) {
        printf("%4d", i);
        printf("  ");
    }
    std::cout << "\n";
    for (Node *p = head; p; p = p->next) {
        printf("%4d", p->data);
        printf("->");
    }
    printf("NULL");
    printf("\n");
}

bool searchLink_1(Node *head, int val) {
    Node *p = head;
    int cnt = 0, flag = 0;
    while (p) {
        if (p->data == val) {
            printLinklist(head);
            int len = 6 * cnt + 3;  // (2 * n - 2) * cnt + n - 1  n = 4 (%4d)
            for (int i = 0; i < len; i++)
                printf(" ");
            printf("^\n");
            for (int i = 0; i < len; i++)
                printf(" ");
            printf("|\n");
            flag++;
        }
        cnt += 1;
        p = p->next;
    }
    if (flag) {
        std::cout << "Find " << flag << " value(s)\n";
        return true;
    } else {
        std::cout << "Not Found\n";
        return false;
    }
}

bool searchLink_2(Node *head, int val) {
    Node *p = head;
    int flag = 0;
    while (p) {
        if (p->data == val) {
            printf("   *");
            printf("  ");
            flag++;
        } else {
            printf("    ");
            printf("  ");
        }
        p = p->next;
    }
    printf("\n");
    if (flag) {
        std::cout << "Find " << flag << " value(s)\n";
        return true;
    } else {
        std::cout << "Not Found\n";
        return false;
    }
}
// 销毁
void destroyLinklist(Node *head) {
    if (head == nullptr)
        return;
    for (Node *p = head, *tmp; p; p = tmp) {
        tmp = p->next;
        free(p);
    }
    return;
}

#define MAX_N 10

int main() {
    srand(time(0));
    Node *new_link = NULL;
    for (int i = 0; i < MAX_N; i++) {
        int pos = rand() % (i + 1);
        int val = rand() % 100;
        new_link = insertOpt(new_link, pos, val);
        printf("Insert %d at %d\n\n", val, pos);
        printLinklist(new_link);
    }
    int val;
    while (~scanf("%d", &val)) {
        printLinklist(new_link);
        searchLink_2(new_link, val);
    }
    destroyLinklist(new_link);
    return 0;
}
